package 学习计划.数据结构;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/pascals-triangle-ii/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6
 */
public class _119_杨辉三角II {
    /**
     * 执行用时：1ms，内存消耗：39.4MB
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            List<Integer> curr = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    curr.add(1);
                } else {
                    curr.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = curr;
        }
        return pre;
    }

    /**
     * 执行用时：1ms，内存消耗：39.2MB
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow2(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        row.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            row.add(0);
            for (int j = i; j > 0; --j) {
                row.set(j, row.get(j - 1) + row.get(j));
            }
        }
        return row;
    }

    /**
     * 执行用时：1ms，内存消耗：39MB
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow3(int rowIndex) {
        List<Integer> ret = new ArrayList<>();
        ret.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            ret.add((int) ((long) ret.get(i - 1) * (rowIndex - i + 1) / i));
        }
        return ret;
    }

    public static void main(String[] args) {

    }
}
